Na vstupu je dána posloupnost kladných celých čísel, Čísla se mohou v posloupnosti libovolně opakovat. Navrhněte efektivní algoritmus, který v posloupnosti určí délku maximálního souvislého úseku, který se v posloupnosti nachází alespoň dvakrát. Oba výskyty úseku se mohou (ale nemusí) částečně překrývat.
Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou složitostí vzhledem k délce posloupnosti n. Plný počet bodů bude udělen jen za řešení v čase O(n2) a pracovní paměti O(1) (tj. můžeme předpokládat, že vstup je uložen v datové struktuře typu pole, z níž můžeme - i opakovaně - číst, další datové struktury by ovšem měly zabírat pouze paměť konstantní velikosti).
(a) Popište algoritmus (včetně datových struktur, které případně budete používat). Programový kód není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Budete-li používat nějakou pomocnou datovou strukturu, nezapomeňte popsat složitost operací nad ní prováděných.
(b) Zdůvodněte správnost algoritmu.
(c) Odvoďte asymptotickou časovou a prostorovou složitost (v nejhorším případě).
Příklad:
vstup: 5 3 1 4 1 5 9 3 1 4 1 5 9 3 1 9
výstup: 8
Poznámka: Úlohu lze vyřešit v lineárním čase, příslušný algoritmus ovšem nespadá do učiva 1. ročníku.
-------------------------------------------------------------<
Je zadán binární strom o n vrcholech, v nichž jsou uložena celá čísla. Navrhněte efektivní algoritmus, který ve stromu najde podstrom s minimálním součtem hodnot všech svých listů. Funkce vrátí jako svůj výsledek hodnotu nalezeného minimálního součtu.
Poznámka: Povšimněte si, že čísla uložená ve vrcholech stromu mohou být i záporná, a podstrom může být tvořen i jediným vrcholem (tj. listem zkoumaného stromu).
(a) Svoje řešení zapište jako funkci v Pythonu, využijte definici třídy pro vrchol binárního stromu uvedenou níže a váš kód prosím opatřete komentáři,
(b) zdůvodněte správnost,
(c) odvoďte časovou a prostorovou složitost (do prostorové složitosti počítejte jen paměť, do níž se zapisuje). Pracuje vaše řešení v asymptoticky optimálním čase a prostoru?
class VrcholBinStromu:
"""třída pro reprezentaci vrcholu binárního stromu"""
def __init__(self, info = None, levy = None, pravy = None):
self.info = info # data
self.levy = levy # levé dítě
self.pravy = pravy # pravé dítě
def minListy(koren : VrcholBinStromu) -> int :
"""
koren : kořen zadaného binárního stromu
vrátí : minimální součet hodnot listů podstromu
"""
-------------------------------------------------------------<
Dokažte nebo vyvraťte každé z následujících tvrzení:
(a1) pro libovolné tři funkce f, g, h: N → R+ platí
jestliže f = O( h ) a g = O( h ) , potom f . g = O( h2 )
(a2) pro libovolné tři funkce f, g, h: N → R+ platí
jestliže f . g = O( h2 ) , potom f = O( h ) a g = O( h )
Svoji odpověď zdůvodněte, tj. tvrzení dokažte (pokud platí) či sestrojte protipříklad (pokud neplatí). Nestačí jen napsat, že je to triviální či že to bylo na přednášce / cvičeních apod.
(b) Složitost problému vyhledání zadaného prvku v setříděném poli délky n porovnávacím algoritmem je Θ(log n).
Porovnávací algoritmus přistupuje k prvkům zadaným na vstupu prostřednictvím operace porovnání dvou prvků
x < y , x > y , x ≤ y , x ≥ y , x = y ,
hodnoty prvků jinak nevyužívá.